/*!
 * \file Graph.h
 * \brief A data structure representing a Simple Graph.
 *
 * \see Graphs
 *
 * \date Jun 18, 2012
 * \author correa
 */

#ifndef GRAPH_H_
#define GRAPH_H_

#include <cstdio>
#include <math.h>
#include "BitMapDirectlyAddressedSet.h"
#include "BitTools.h"


typedef enum GT { GT_GRAPH, GT_COMPLEMENT } graphType;//!< the type of the graph

template<class D> class Graph<D>;

/*! \class DiGraph
 * \brief A directed graph with the vertices being natural numbers
 *
 * A DiGraph is a pair of a set of vertices and a binary relation as a set of edges.
 * This class implements a directed graph, that is a graph where edges \c (i, \c j)
 * and \c (j, \c i) are distinct.
 *
 * The set of vertices is a assumed to be a set of natural numbers. More precisely, if \c n is the
 * number of vertices in the graph, then the vertices are identified by natural numbers in the interval \c [0, \c ..., \c n \c - \c 1].
 */
template<class D>
class DiGraph {
	friend class Graph<D>;	//!< this allows the Graph to have access to \c adj directly

	D ** const adj;	//!< the adjacent matrix of the graph

protected:

	const long 	n;						//!< number of vertices in the graph
	long 		m;						//!< number of edges

	/*!
	 * \brief A simple constructor.
	 *
	 * A simple constructor used internally to allocate memory for a general object of this
	 * class.
	 *
	 */
	DiGraph(long n);

public:

	/*!
	 * \brief The destructor
	 *
	 * Clean all the information used by a object of this class
	 *
	 * */
	virtual ~DiGraph();

	/*!
	 * \brief The number of vertices
	 *
	 * Return the cardinality of the vertex set.
	 *
	 * \return the number of vertices in the graph
	 */
	virtual long nverts() const;

	/*!
	 * \brief Computes the number of edges
	 *
	 * Returns the cardinality of the edge set. It is implemented by a call to DirectlyAddressedSet::cardOfSet() in
	 * each line of the adjacency matrix and summing up the results.
	 *
	 * \return the number of edges
	 */
	virtual long countnedges();

	/*!
	 * \brief Returns the number of edges
	 *
	 * Returns the cardinality of the edge set obtained with last invocation to countnedges().
	 *
	 * \return the number of edges
	 * */
	virtual long nedges() const;

	/*!
	 * \brief Adds an edge between the two specified vertices (optional operation).
	 *
	 * Adds the second specified vertex to the neighborhood of the first vertex.
	 * A further call to hasEdge(firstVertex, secondVertex) returns \c true unless delEdge() or
	 * delAllEdges() is invoked to delete the edge defined by the specified vertices.
	 *
	 * An invocation of this method does not affect the result of hasEdge(secondVertex, firstVertex).
	 *
	 * If one of the specified elements is out of the universe an error will occur.
	 *
	 * \param i the first vertex
	 * \param j the second vertex
	 * */
	virtual void addEdge(long i, long j);

	/*!
	 * \brief Deletes the edge defined by the two specified vertices (optional operation).
	 *
	 * Deletes the second specified vertex from the neighborhood of the first vertex.
	 * A further call to hasEdge(firstVertex, secondVertex) returns \c false unless addEdge() or
	 * addAllEdges() is invoked to add the edge defined by the specified vertices.
	 *
	 * An invocation of this method does not affect the result of hasEdge(secondVertex, firstVertex).
	 *
	 * If one of the specified elements is out of the universe an error will occur.
	 *
	 * \param i the first vertex
	 * \param j the second vertex
	 *
	 */
	virtual void delEdge(long i, long j);

	/*!
	 * \brief Swap the edge represented by the specified ordered pair (optional operation).
	 *
	 * If the edge represented by the specified ordered pair is in the graph,
	 * it will be removed if not it will be added.
	 *
	 * \param i first vertex
	 * \param j second vertex
	 *
	 */
	virtual void flipEdge(long i, long j);

	/*!
	 * \brief Adds all possible edges (optional operation).
	 *
	 * A further call to hasEdge(i, j), for any pair \c i and \c j of vertices, returns \c true unless delEdge() or
	 * delAllEdges() is invoked to delete the edge involved in the query.
	 *
	 * It transforms the graph in a complete graph.
	 *
	 * */
	virtual void addAllEdges();

	/*!
	 * \brief Removes all possible edges (optional operation).
	 *
	 * A further call to hasEdge(i, j), for any pair \c i and \c j of vertices, returns \c false unless addEdge() or
	 * addAllEdges() is invoked to add the edge involved in the query.
	 *
	 * It transforms the graph in a empty graph.
	 *
	 * */
	virtual void delAllEdges();

	/*!
	 * \brief Queries for an edge.
	 *
	 * If one of the specified vertices is out of the universe an error will occur.
	 *
	 * \param i the first vertex
	 * \param j the second vertex
	 *
	 * \return \c true if the edge defined by \c i and \c j, in this order, is in the edge set, otherwise returns \c false.
	 * */
	virtual bool hasEdge(long i, long j) const;

	/*!
	 * \brief The number of neighbors of a specified vertex.
	 *
	 * Count the number of neighbors of a specified vertex. A vertex \c j is a neighbor of the
	 * specified vertex if \c hasEdge(i, \c j) returns \c true. It is implemented using
	 * the function DirectlyAddressedSet::cardOfSet().
	 *
	 * If the element is out of the universe, an error will occur.
	 *
	 * \param i the specified vertex.
	 *
	 * \return the number of neighbors of the specified vertex.
	 * */
	virtual long degree(long i) const;

	/*!
	 * \brief The number of anti-neighbors of a specified vertex.
	 *
	 * Count the number of anti-neighbors of a specified vertex. A vertex \c j is a neighbor of the
	 * specified vertex if \c hasEdge(i, \c j) returns \c false. It is implemented using
	 * the function DirectlyAddressedSet::cardOfCompl().
	 *
	 * If the element is out of the universe, an error will occur.
	 *
	 * \param i the specified vertex.
	 *
	 * \return the number of anti-neighbors of the specified vertex.
	 * */
	virtual long antiDegree(long i) const;

	/*!
	 * \brief Retrieves the neighborhood of a specified vertex as an unmodifiable DirectlyAddressedSet.
	 *
	 * This graph is backed by the returned set.
	 *
	 * If the
	 * specified element is out of the universe an error will occur.
	 *
	 * \param i the specified vertex.
	 *
	 * \return neighborhood of a specified vertex as a DirectlyAddressedSet.
	 */
	virtual const D * neig(long i) const = 0;

	/*!
	 * \brief Joins the neighborhood of two specified vertices (optional operation).
	 *
	 * Adds all the neighbors of the second specified element to the neighborhood of the
	 * first specified vertex. It is implemented using the method DirectlyAddressedSet::addAll().
	 * The result overwrite the neigbourhood of the first element.
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * \param i the first specified element.
	 * \param j the second specified element.
	 *
	 * \return the resulting \c i's neighborhood
	 *
	 * \see DirectlyAddressedSet::addAll()
	 * */
	virtual void joinAdj(long i, long j);

	/*!
	 * \brief Calculates the common neighborhood of specified vertices (optional operation)
	 *
	 * Retains in the neigbourhood of the first element the neighbors of the second vertex only.
	 * It is implemented using the method DirectlyAddressedSet::retainAll().
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * \param i the first specified element.
	 * \param j the second specified element.
	 *
	 * \return the resulting \c i's neighborhood
	 *
	 * \see DirectlyAddressedSet::retainAll()
	 * */
	virtual void commonAdj(long i, long j);

	/*!
	 * \brief Removes from the neighborhood of one specified vertex the neighbors of a second specified vertex (optional operation)
	 *
	 * Removes all the neighbors of the second specified element to the neighborhood of the
	 * first specified vertex. It is implemented using the method DirectlyAddressedSet::removeAll().
	 * The result overwrite the neighborhood of the first element.
	 *
	 * If one of the elements is out of the universe, an error will occur.
	 *
	 * \param i the first specified element.
	 * \param j the second specified element.
	 *
	 * \return the resulting \c i's neighborhood
	 *
	 * \see DirectlyAddressedSet::removeAll()
	 * */
	virtual void diffAdj(long i, long j);

	/*!
	 * \brief Create a clone of the current graph.
	 *
	 * Create a clone of the current graph, with the same number of edges, the same
	 * vertex set and the same edges. It is implemented using the method clone
	 * to each line of the adjacency matrix.
	 *
	 * \return a copy of the current graph.
	 */
	virtual DiGraph<D> * clone() const = 0;

	/*!
	 * \brief Create the square of the current graph.
	 *
	 * The square of a graph \c G is a graph with the same set of vertex and all the edges
	 * in the egdes of \c G and the edges \c uv such that exists in \c G the edges \c uw and
	 * \c vw for some vertex \c w in the vertex set.
	 *
	 * \return the square graph of the current graph.
	 * */
	virtual DiGraph<D> * square() const;

	/*!
	 * \brief Determine wherever or not the relation over the graph is empty.
	 *
	 * A graph is considered empty, if its edge set is empty.
	 *
	 * \return \c true if the current graph has no edges, and \c false otherwise.
	 * */
	virtual bool isEmpty();

	//DEBUG
	virtual void show();
};

template<class D>
inline DiGraph<D>::DiGraph(long n) : n(n), m(0), adj(new D *[n]) {
}

template<class D>
inline DiGraph<D>::~DiGraph() {
	for(long i = 0; i < n; i++)
		if (adj[i] != NULL)
			delete adj[i];
	delete[] adj;
}

template<class D>
inline long DiGraph<D>::nverts() const {
	return n;
}

template<class D>
inline long DiGraph<D>::nedges() const {
	return m;
}

template<class D>
inline void DiGraph<D>::joinAdj(long i, long j) {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	if (adj[j] == NULL)
		adj[j] = neig(j);
	adj[i]->addAll(adj[j]);
}

template<class D>
inline void DiGraph<D>::commonAdj(long i, long j) {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	if (adj[j] == NULL)
		adj[j] = neig(j);
	adj[i]->retainAll(adj[j]);
}

template<class D>
inline void DiGraph<D>::diffAdj(long i, long j) {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	if (adj[j] == NULL)
		adj[j] = neig(j);
	adj[i]->removeAll(adj[j]);
}

template<class D>
inline long DiGraph<D>::countnedges() {
	m = 0;
	for(long i = 0; i < n; i++) {
		if (adj[i] == NULL)
			adj[i] = neig(i);
		m += adj[i]->cardOfSet();
	}
	return m;
}

template<class D>
inline void DiGraph<D>::addEdge(long i, long j) {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	adj[i]->toSet(j);
}

template<class D>
inline void DiGraph<D>::delEdge(long i, long j) {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	adj[i]->toCompl(j);
}

template<class D>
inline void DiGraph<D>::flipEdge(long i, long j) {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	return adj[i]->flip(j);
}

template<class D>
inline bool DiGraph<D>::hasEdge(long i, long j) const {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	return adj[i]->isInSet(j);
}

template<class D>
inline void DiGraph<D>::addAllEdges() {
	for(long i = 0; i < n; i++) {
		if (adj[i] == NULL)
			adj[i] = neig(i);
		adj[i]->allToSet();
	}
}

template<class D>
inline void DiGraph<D>::delAllEdges() {
	for(long i = 0; i < n; i++) {
		if (adj[i] == NULL)
			adj[i] = neig(i);
		adj[i]->allToCompl();
	}
}

template<class D>
inline long DiGraph<D>::degree(long i) const {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	return adj[i]->cardOfSet();
}

template<class D>
inline long DiGraph<D>::antiDegree(long i) const {
	if (adj[i] == NULL)
		adj[i] = neig(i);
	return n - adj[i]->cardOfSet() - 1;
}

template<class D>
inline DiGraph * DiGraph<D>::square() const {
	//clone the current graph
	DiGraph * g = clone();

	//add the transitive edges
	for(long i = 0; i < n; i++) {
		if (adj[i] == NULL)
			adj[i] = neig(i);
		DirectlyAddressedSet::Iterator * it = adj[i]->newIterator();
		long iu = adj[i]->universeSize();
		long j = it->next();
		while (j < iu) {
			if (adj[j] == NULL)
				adj[j] = neig(i);
			g->adj[i]->addAll(adj[j]);
			it->next();
		}
	}
	return g;
}

template <typename T>
class BitMap {
protected:
	long long		matrixsize;
	int				logrowsize;

	BitMap(long n, BitTools<T> * bt);
	size_t rowIndex(const int i) const;
	size_t pairIndex(const int i, const int j, BitTools<T> * bt) const;
};

template <typename T>
inline BitMap<T>::BitMap(long n, BitTools<T> * bt) {
	logrowsize = bt->inline_ceillog(n,2);
	if (logrowsize < 0)
		logrowsize = 0;
	matrixsize = (1LL << logrowsize)*n;
}

template <typename T>
inline size_t BitMap<T>::rowIndex(const int i) const {
	return (i << logrowsize);
}

template <typename T>
inline size_t BitMap<T>::pairIndex(const int i, const int j, BitTools<T> * bt) const {
	return rowIndex(i)+(j >> bt->logb);
}

template <class T>
class BitMapDiGraph : private BitMap<T>, protected T, public DiGraph {

public:
	BitMapDiGraph(long n);
	virtual ~BitMapDiGraph();

	virtual const T * neig(long i) const;
	virtual DiGraph<T> * clone() const;

	virtual long nedges();
	virtual long countnedges();
	virtual void addEdge(long i, long j);
	virtual void delEdge(long i, long j);
	virtual void flipEdge(long i, long j);
	virtual void addAllEdges();
	virtual void delAllEdges();
	virtual bool hasEdge(long i, long j) const;

};

template <class T>
inline BitMapDiGraph<T>::BitMapDiGraph(long n) : BitMap<T>(n,this), T(this->matrixsize), DiGraph(n) {

}

template <class T>
inline BitMapDiGraph<T>::~BitMapDiGraph() {
}

template<class T>
inline const T * BitMapDiGraph<T>::neig(long i) const {
	return (const T *) set->subset(i << this->logrowsize, i+(1LL << this->logrowsize));
}

template<class T>
inline DiGraph<T> * BitMapDiGraph<T>::clone() const {
	//TODO
	DiGraph * g = new BitMapDiGraph<T>(n);
	return g;
}

template <class T>
inline long BitMapDiGraph<T>::countnedges() {
	return cardOfSet();
}

template<class T>
inline void BitMapDiGraph<T>::addEdge(long i, long j) {
	toSet(pairIndex(i, j, this));
}

template<class T>
inline void BitMapDiGraph<T>::delEdge(long i, long j) {
	toCompl(pairIndex(i, j, this));
}

template<class T>
inline void BitMapDiGraph<T>::flipEdge(long i, long j) {
	return flip(pairIndex(i, j, this));
}

template<class T>
inline bool BitMapDiGraph<T>::hasEdge(long i, long j) const {
	return isInSet(pairIndex(i, j, this));
}

template<class T>
inline void BitMapDiGraph<T>::addAllEdges() {
	allToSet();
}

template<class T>
inline void BitMapDiGraph<T>::delAllEdges() {
	allToCompl();
}

template <class T>
class BitMapsDiGraph : public DiGraph<T> {
	Factory<T> * const 	factory;
	T ** const 			adj;		//!< The adjacent matrix of the graph

public:
	BitMapsDiGraph(T * set);
	BitMapsDiGraph(long n, Factory<T> * factory);
	BitMapsDiGraph(long n, Factory<T> * factory, void * handle);
	BitMapsDiGraph(long n, Factory<T> * factory, void** handle);
	virtual ~BitMapsDiGraph();

	virtual const T * neig(long i) const;
	virtual DiGraph<T> * clone() const;

	virtual long nedges();
	virtual void addEdge(long i, long j);
	virtual void delEdge(long i, long j);
	virtual void flipEdge(long i, long j);
	virtual void addAllEdges();
	virtual void delAllEdges();
	virtual bool hasEdge(long i, long j) const;
	virtual void joinAdj(long i, long j);
	virtual void commonAdj(long i, long j);
	virtual void diffAdj(long i, long j);
	virtual long countnedges();
	virtual long degree(long i) const;
	virtual long antiDegree(long i) const;
	virtual DiGraph<T> * square() const;

};

template <class T>
inline BitMapsDiGraph<T>::BitMapsDiGraph(T * set) : DiGraph<T>(set->universeSize()), factory(NULL), adj(new T*[n]) {
	long long nn = n*n;
	for(long i = 0; i < nn; i+=n)
		adj[i] = (T *) set->subset(i, i+n);
	m = countnedges();
}

template <class T>
inline BitMapsDiGraph<T>::BitMapsDiGraph(long n, Factory<T> * factory) : DiGraph<T>(n), factory(factory), adj(new T*[n]) {
	for(long i = 0; i < n; i++)
		adj[i] = (T *) factory->newInstance(n);
	m = 0;
}

template <class T>
inline BitMapsDiGraph<T>::BitMapsDiGraph(long n, Factory<T> * factory, void * handle) : DiGraph<T>(n), factory(factory), adj(new T*[n]) {
	for(long i = 0; i < n; i++)
		adj[i] = (T *) factory->newInstance(n, handle);
	m = countnedges();
}

template <class T>
inline BitMapsDiGraph<T>::BitMapsDiGraph(long n, Factory<T> * factory, void** handle) : DiGraph(n), factory(factory), adj(new T*[n]) {
	for(long i = 0; i < n; i++)
		adj[i] = (T *) factory->newInstance(n, handle[i]);
	m = countnedges();
}

template <class T>
inline BitMapsDiGraph<T>::~BitMapsDiGraph() {
	for(long i = 0; i < n; i++)
		delete adj[i];
	delete[] adj;
}

template<class T>
inline const T * BitMapsDiGraph<T>::neig(long i) const {
	return (const T *) adj[i]->subset(0, adj[i]->universeSize());
}

template<class T>
inline DiGraph<T> * BitMapsDiGraph<T>::clone() const {
	//TODO
	DiGraph * g = new BitMapDiGraph<T>(n);
	return g;
}

template<class T>
inline void BitMapsDiGraph<T>::joinAdj(long i, long j) {
	adj[i]->addAll(adj[j]);
}

template<class T>
inline void BitMapsDiGraph<T>::commonAdj(long i, long j) {
	adj[i]->retainAll(adj[j]);
}

template<class T>
inline void BitMapsDiGraph<T>::diffAdj(long i, long j) {
	adj[i]->removeAll(adj[j]);
}

template<class T>
inline long BitMapsDiGraph<T>::countnedges() {
	m = 0;
	for(long i = 0; i < n; i++)
		m += adj[i]->cardOfSet();
	return m;
}

template<class T>
inline void BitMapsDiGraph<T>::addEdge(long i, long j) {
	adj[i]->toSet(j);
}

template<class T>
inline void BitMapsDiGraph<T>::delEdge(long i, long j) {
	adj[i]->toCompl(j);
}

template<class T>
inline void BitMapsDiGraph<T>::flipEdge(long i, long j) {
	adj[i]->flip(j);
}

template<class T>
inline bool BitMapsDiGraph<T>::hasEdge(long i, long j) const {
	return adj[i]->isInSet(j);
}

template<class T>
inline void BitMapsDiGraph<T>::addAllEdges() {
	for(long i = 0; i < n; i++)
		adj[i]->allToSet();
}

template<class T>
inline void BitMapsDiGraph<T>::delAllEdges() {
	for(long i = 0; i < n; i++)
		adj[i]->allToCompl();
}

template<class T>
inline long BitMapsDiGraph<T>::degree(long i) const {
	return adj[i]->cardOfSet();
}

template<class T>
inline long BitMapsDiGraph<T>::antiDegree(long i) const {
	return n - adj[i]->cardOfSet() - 1;
}

template<class T>
inline DiGraph<T> * BitMapsDiGraph<T>::square() const {
	//clone the current graph
	DiGraph<T> * g = clone();

	//add the transitive edges
	for(long i = 0; i < n; i++) {
		DirectlyAddressedSet::Iterator * it = adj[i]->newIterator();
		long iu = adj[i]->universeSize();
		long j = it->next();
		while (j < iu) {
			g->adj[i]->addAll(adj[j]);
			it->next();
		}
	}
	return g;
}

/*!
 * \class Graph
 */
template<class D>
class Graph : public DiGraph<D> {
	Graph(long n) : DiGraph<D>(n) {};
	virtual ~Graph();

	/*!
	 * \brief Adds an edge between the two specified vertices (optional operation).
	 *
	 * Adds one specified vertex to the neighborhood of the other.
	 * A further call to hasEdge(firstVertex, secondVertex) or hasEdge(secondVertex, firstVertex)returns \c true unless delEdge() or
	 * delAllEdges() is invoked to delete the edge defined by the specified vertices.
	 *
	 * If one of the specified elements is out of the universe an error will occur.
	 *
	 * \param i the first vertex
	 * \param j the second vertex
	 * */
	virtual void addEdge(long i, long j);

	/*!
	 * \brief Deletes the edge defined by the two specified vertices (optional operation).
	 *
	 * Deletes one specified vertex from the neighborhood of the other.
	 * A further call to hasEdge(firstVertex, secondVertex) or hasEdge(secondVertex, firstVertex) returns \c false unless addEdge() or
	 * addAllEdges() is invoked to add the edge defined by the specified vertices.
	 *
	 * If one of the specified elements is out of the universe an error will occur.
	 *
	 * \param i the first vertex
	 * \param j the second vertex
	 *
	 */
	virtual void delEdge(long i, long j);

	/*!
	 * \brief Swap the edge represented by the specified ordered pair (optional operation).
	 *
	 * If the edge represented by the specified ordered pair is in the graph,
	 * it will be removed if not it will be added.
	 *
	 * \param i first vertex
	 * \param j second vertex
	 *
	 */
	virtual void flipEdge(long i, long j);

	virtual void joinAdj(long i, long j);
	virtual void commonAdj(long i, long j);
	virtual void diffAdj(long i, long j);

	/*!
	 * \brief Creates a homomorphism of the current graph
	 *
	 * A homomorphism of a graph is a labeling function *l* of its vertex such that if ij is a edge
	 * than l(i)l(j) is an edge and is ij is not an edge than ij is not an edge.
	 *
	 * The array passed as parameter is the labeling function, the position i represents the new
	 * label of the vertex i. the long is the size of the array.
	 *
	 * Notice that is not necessary that the array has a position to every vertex, and you can
	 * associate more than one vertex to a same label. But it can cause bad behaive of the functions.
	 *
	 * \param rsize the size of the array \c R, in bytes
	 * \param R the labeling function, each position represents the new label of the vertex in that
	 * position.
	 *
	 * \return A homomorphism of the current graph represented by \c R as the labeling function.
	 *
	 * */
	virtual DiGraph * homomorphism(long rsize, char * R);

	/*!
	 * \brief The complement of the current graph.
	 *
	 * The complement of a graph is another graph that has the same set of vertexes but the set of
	 * edges is different. If uv is an edge in the graph if is not in the complement, if is not an edge
	 * in the graph is in the complement, except for the edges in the form vv.
	 *
	 *
	 * \return the complement of the current graph.
	 * */
	virtual DiGraph * complement();
};

template<class D>
inline void Graph<D>::addEdge(long i, long j) {
	DiGraph<D>::addEdge(i, j);
	DiGraph<D>::addEdge(j, i);
}

template<class D>
inline void Graph<D>::delEdge(long i, long j) {
	DiGraph<D>::delEdge(i, j);
	DiGraph<D>::delEdge(j, i);
}

template<class D>
inline void Graph<D>::flipEdge(long i, long j) {
	DiGraph<D>::flipEdge(i, j);
	DiGraph<D>::flipEdge(j, i);
}

template<class D>
inline void Graph<D>::joinAdj(long i, long j) {
	DiGraph<D>::joinAdj(i, j); // this call assures that adj[j] != NULL

	DirectlyAddressedSet::Iterator * it = adj[j]->newIterator();
	long l = it->next();
	long iu = adj[j]->universeSize();
	while (l < iu) {
		DiGraph<D>::addEdge(l, i);
		it->next();
	}
}

template<class D>
inline void Graph<D>::commonAdj(long i, long j) {
	DiGraph<D>::commonAdj(i, j); // this call assures that adj[j] != NULL

	DirectlyAddressedSet::Iterator * it = adj[i]->newComplIterator();
	long l = it->next();
	long iu = adj[i]->universeSize();
	while (l < iu) {
		DiGraph<D>::delEdge(l, i);
		it->next();
	}
}

template<class D>
inline void Graph<D>::diffAdj(long i, long j) {
	DiGraph<D>::diffAdj(i, j); // this call assures that adj[j] != NULL

	DirectlyAddressedSet::Iterator * it = adj[i]->newComplIterator();
	long l = it->next();
	long iu = adj[i]->universeSize();
	while (l < iu) {
		DiGraph<D>::delEdge(l, i);
		it->next();
	}
}

template <class T>
class BitMapGraph : private BitMap<T>, protected T, public Graph {

public:
	BitMapGraph(long n);
	virtual ~BitMapGraph();

	virtual const T * neig(long i) const;
	virtual DiGraph<T> * clone() const;

	virtual long nedges();
	virtual long countnedges();
	virtual void addEdge(long i, long j);
	virtual void delEdge(long i, long j);
	virtual void flipEdge(long i, long j);
	virtual void addAllEdges();
	virtual void delAllEdges();
	virtual bool hasEdge(long i, long j) const;

};

template <class T>
inline BitMapGraph<T>::BitMapGraph(long n) : BitMap<T>(n,this), T(this->matrixsize), Graph(n) {

}

template <class T>
inline BitMapGraph<T>::~BitMapGraph() {
}

template<class T>
inline const T * BitMapGraph<T>::neig(long i) const {
	return (const T *) set->subset(i << this->logrowsize, i+(1LL << this->logrowsize));
}

template<class T>
inline DiGraph<T> * BitMapGraph<T>::clone() const {
	//TODO
	DiGraph<T> * g = new BitMapDiGraph<T>(n);
	return g;
}

template <class T>
inline long BitMapGraph<T>::countnedges() {
	return cardOfSet();
}

template<class T>
inline void BitMapGraph<T>::addEdge(long i, long j) {
	toSet(pairIndex(i, j, this));
	toSet(pairIndex(j, i, this));
}

template<class T>
inline void BitMapGraph<T>::delEdge(long i, long j) {
	toCompl(pairIndex(i, j, this));
	toCompl(pairIndex(j, i, this));
}

template<class T>
inline void BitMapGraph<T>::flipEdge(long i, long j) {
	flip(pairIndex(i, j, this));
	flip(pairIndex(j, i, this));
}

template<class T>
inline bool BitMapGraph<T>::hasEdge(long i, long j) const {
	return isInSet(pairIndex(i, j, this));
}

template<class T>
inline void BitMapGraph<T>::addAllEdges() {
	allToSet();
}

template<class T>
inline void BitMapGraph<T>::delAllEdges() {
	allToCompl();
}

template <class T>
class BitMapsGraph : public Graph<T> {
	Factory<T> * const 	factory;
	T ** const 			adj;		//!< The adjacent matrix of the graph

public:
	BitMapsGraph(T * set);
	BitMapsGraph(long n, Factory<T> * factory);
	BitMapsGraph(long n, Factory<T> * factory, void * handle);
	BitMapsGraph(long n, Factory<T> * factory, void** handle);
	virtual ~BitMapsGraph();

	virtual const T * neig(long i) const;
	virtual DiGraph<T> * clone() const;

	virtual long nedges();
	virtual void addEdge(long i, long j);
	virtual void delEdge(long i, long j);
	virtual void flipEdge(long i, long j);
	virtual void addAllEdges();
	virtual void delAllEdges();
	virtual bool hasEdge(long i, long j) const;
	virtual void joinAdj(long i, long j);
	virtual void commonAdj(long i, long j);
	virtual void diffAdj(long i, long j);
	virtual long countnedges();
	virtual long degree(long i) const;
	virtual long antiDegree(long i) const;
	virtual DiGraph<T> * square() const;

};

template <class T>
inline BitMapsGraph<T>::BitMapsGraph(T * set) : Graph<T>(set->universeSize()), factory(NULL), adj(new T*[n]) {
	long long nn = n*n;
	for(long i = 0; i < nn; i+=n)
		adj[i] = (T *) set->subset(i, i+n);
	m = countnedges();
}

template <class T>
inline BitMapsGraph<T>::BitMapsGraph(long n, Factory<T> * factory) : Graph<T>(n), factory(factory), adj(new T*[n]) {
	for(long i = 0; i < n; i++)
		adj[i] = (T *) factory->newInstance(n);
	m = 0;
}

template <class T>
inline BitMapsGraph<T>::BitMapsGraph(long n, Factory<T> * factory, void * handle) : Graph<T>(n), factory(factory), adj(new T*[n]) {
	for(long i = 0; i < n; i++)
		adj[i] = (T *) factory->newInstance(n, handle);
	m = countnedges();
}

template <class T>
inline BitMapsGraph<T>::BitMapsGraph(long n, Factory<T> * factory, void** handle) : Graph(n), factory(factory), adj(new T*[n]) {
	for(long i = 0; i < n; i++)
		adj[i] = (T *) factory->newInstance(n, handle[i]);
	m = countnedges();
}

template <class T>
inline BitMapsGraph<T>::~BitMapsGraph() {
	for(long i = 0; i < n; i++)
		delete adj[i];
	delete[] adj;
}

template<class T>
inline const T * BitMapsGraph<T>::neig(long i) const {
	return (const T *) adj[i]->subset(0, adj[i]->universeSize());
}

template<class T>
inline DiGraph<T> * BitMapsGraph<T>::clone() const {
	//TODO
	DiGraph * g = new BitMapDiGraph<T>(n);
	return g;
}

template<class T>
inline void BitMapsGraph<T>::joinAdj(long i, long j) {
	adj[i]->addAll(adj[j]);

	DirectlyAddressedSet::Iterator * it = adj[j]->newIterator();
	long l = it->next();
	long iu = adj[j]->universeSize();
	while (l < iu) {
		addEdge(l, i);
		it->next();
	}
}

template<class T>
inline void BitMapsGraph<T>::commonAdj(long i, long j) {
	adj[i]->retainAll(adj[j]);

	DirectlyAddressedSet::Iterator * it = adj[i]->newComplIterator();
	long l = it->next();
	long iu = adj[i]->universeSize();
	while (l < iu) {
		delEdge(l, i);
		it->next();
	}
}

template<class T>
inline void BitMapsGraph<T>::diffAdj(long i, long j) {
	adj[i]->removeAll(adj[j]);

	DirectlyAddressedSet::Iterator * it = adj[i]->newComplIterator();
	long l = it->next();
	long iu = adj[i]->universeSize();
	while (l < iu) {
		delEdge(l, i);
		it->next();
	}
}

template<class T>
inline long BitMapsGraph<T>::countnedges() {
	m = 0;
	for(long i = 0; i < n; i++)
		m += adj[i]->cardOfSet();
	return m;
}

template<class T>
inline void BitMapsGraph<T>::addEdge(long i, long j) {
	adj[i]->toSet(j);
	adj[j]->toSet(i);
}

template<class T>
inline void BitMapsGraph<T>::delEdge(long i, long j) {
	adj[i]->toCompl(j);
	adj[j]->toCompl(i);
}

template<class T>
inline void BitMapsGraph<T>::flipEdge(long i, long j) {
	adj[i]->flip(j);
	adj[j]->flip(i);
}

template<class T>
inline bool BitMapsGraph<T>::hasEdge(long i, long j) const {
	return adj[i]->isInSet(j);
}

template<class T>
inline void BitMapsGraph<T>::addAllEdges() {
	for(long i = 0; i < n; i++)
		adj[i]->allToSet();
}

template<class T>
inline void BitMapsGraph<T>::delAllEdges() {
	for(long i = 0; i < n; i++)
		adj[i]->allToCompl();
}

template<class T>
inline long BitMapsGraph<T>::degree(long i) const {
	return adj[i]->cardOfSet();
}

template<class T>
inline long BitMapsGraph<T>::antiDegree(long i) const {
	return n - adj[i]->cardOfSet() - 1;
}

template<class T>
inline DiGraph<T> * BitMapsGraph<T>::square() const {
	//clone the current graph
	DiGraph<T> * g = clone();

	//add the transitive edges
	for(long i = 0; i < n; i++) {
		DirectlyAddressedSet::Iterator * it = adj[i]->newIterator();
		long iu = adj[i]->universeSize();
		long j = it->next();
		while (j < iu) {
			g->adj[i]->addAll(adj[j]);
			it->next();
		}
	}
	return g;
}

/*!
 * \class DiGraphFactory
 */
template<class D>
class DiGraphFactory : public Factory<DiGraph<D> > {
public:
	virtual ~DiGraphFactory() {};

	/*!
	 *
	 * \param n number of vertices
	 */
	virtual DiGraph<D> * newInstance(long n) = 0;
	virtual DiGraph<D> * newInstance(long n, void * handle) = 0;
};

#endif /* GRAPH_H_ */
